Maratones competidas/Maratón Nacional 2011/workspace/c/c6.cpp

   1 // Equipo Poncho, Carriel y Ruana
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x)
  23 { stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x)
  25 { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl;
  30
  31 const double EPS = 1e-9;
  32
  33 int cmp(double x, double y = 0, double tol = EPS) {
  34     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35 }
  36
  37 #define INPUT_FILE "compression"
  38
  39 const int MAXBASES = 105, oo = 1 << 28;
  40 int bases[MAXBASES];
  41
  42 int B, D;
  43 int bit[20]; // bit[i] = index of term i in the document
  44
  45 int dp[MAXBASES][1 << 16];
  46 int currentRun = 1;
  47 int been[MAXBASES][1 << 16];
  48
  49 int docSize;
  50
  51 void binary(int x){
  52     for (int i = 0; i < 16; ++i){
  53         printf("%d", !!(x & (1 << i)));
  54     }
  55 }
  56
  57 void precompute(){
  58     dp[0][0] = 0;
  59     been[0][0] = currentRun;
  60
  61     for (int i = 0; i < B; ++i) {
  62         for (int mask = 0; mask < (1 << 16); ++mask) {
  63             if (been[i][mask] < currentRun) continue;
  64
  65             int base = bases[i];
  66             dp[i+1][mask] = min(dp[i+1][mask], dp[i][mask]);
  67             dp[i+1][mask | base] = min(dp[i+1][mask | base], dp[i][mask] + 1);
  68         }
  69     }
  70 }
  71
  72 void solve(int doc) {
  73
  74     //For(i, 0, B) if (compatible(bases[i])) printf("Base i=%d: %d\n", i, maskOfBase(bases[i]));
  75
  76   //  for (int i = 0; i < 16; ++i) {
  77 //        printf("bit[%d] = %d\n", i, bit[i]);
  78 //    }
  79
  80     int ans = dp[B][doc];
  81     if (ans >= oo) ans = 0;
  82     printf("%d", ans);
  83 }
  84
  85 int main(){
  86     freopen(INPUT_FILE ".in", "r", stdin);
  87     while (cin >> B >> D) {
  88         if (B == 0 and D == 0) break;
  89         for (int i = 0; i < B; ++i) {
  90             bases[i] = 0;
  91
  92             int k; cin >> k;
  93             while (k--) {
  94                 int x; cin >> x; x--;
  95                 bases[i] |= (1 << x);
  96             }
  97             //printf("base[i=%d] = %d\n", i, bases[i]);
  98         }
  99         precompute();
 100         for (int j = 0; j < D; ++j) {
 101             int doc = 0;
 102             cin >> docSize;
 103             int k = docSize;
 104             while (k--) {
 105                 int x; cin >> x; x--;
 106                 doc |= (1 << x);
 107             }
 108             //printf("doc = %d\n", doc);
 109             solve(doc);
 110             if (j + 1 < D) printf(" ");
 111         }
 112         puts("");
 113         currentRun++;
 114
 115     }
 116     return 0;
 117
 118 }